package _剑指offer.二叉树;

import util.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 二叉搜索树的中序遍历为 递增序列 ，所以，如果先 遍历右子树，再访问根节点，再遍历左子树，即可得到递减序列
 */
public class _54_二叉搜索树的第k大节点 {
    @Test
    public void main() {
        Integer[] input = new Integer[]{5,3,6,2,4,null,null,1};
        TreeNode root = TreeNode.getTreeFromArray(input);
        System.out.println(Arrays.toString(input));
        System.out.println("kthLargest(root, 3) = " + kthLargest(root, 3));
    }
    public int kthLargest(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>(); 
        dfs(root, list);
        return list.get(k-1);
    }
    public void dfs(TreeNode root, List<Integer> list) {
        if(root==null) return ;
        dfs(root.right, list);
        list.add(root.val);
        dfs(root.left, list);
    }
    
    @Test
    public void main2() {
        Integer[] input = new Integer[]{5,3,6,2,4,null,null,1};
        TreeNode root2 = TreeNode.getTreeFromArray(input);
        System.out.println(Arrays.toString(input));
        System.out.println("kthLargest2(root2, 3) = " + kthLargest2(root2, 3));
    }
    private int result, k;
    public int kthLargest2(TreeNode root, int k) {
        this.k = k;
        dfs2(root);
        return result;
    }
    public void dfs2(TreeNode root) {
        if(root == null || k == 0) return;
        dfs2(root.right);
        if(--k == 0) result = root.val;
        dfs2(root.left);
    }
    
}
